//
// Created by lanlu on 2025/8/6.
//
class Solution {
public:
    int maxSumTwoNoOverlap(vector<int>& nums, int firstLen, int secondLen) {
        int n = nums.size();
        vector<int> prefix(n + 1, 0);
        for (int i = 0; i < n; ++i) {
            prefix[i + 1] = prefix[i] + nums[i];
        }

        vector<int> firstSums(n - firstLen + 1);
        for (int i = 0; i <= n - firstLen; ++i) {
            firstSums[i] = prefix[i + firstLen] - prefix[i];
        }

        vector<int> secondSums(n - secondLen + 1);
        for (int i = 0; i <= n - secondLen; ++i) {
            secondSums[i] = prefix[i + secondLen] - prefix[i];
        }

        int maxSum = INT_MIN;

        // 情况1：firstLen子数组在secondLen子数组之前
        int maxFirst = INT_MIN;
        for (int j = 0; j < secondSums.size(); ++j) {
            // first子数组必须在second子数组开始前结束
            int iEnd = j - 1;  // first子数组的结束索引
            int iMax = iEnd - firstLen + 1;  // first子数组的最大起始索引

            if (iMax >= 0) {
                // 更新first子数组的最大和
                if (maxFirst == INT_MIN) {
                    // 初始化maxFirst
                    for (int k = 0; k <= iMax; ++k) {
                        maxFirst = max(maxFirst, firstSums[k]);
                    }
                } else {
                    // 只需要检查新增加的可能的i
                    maxFirst = max(maxFirst, firstSums[iMax]);
                }
                maxSum = max(maxSum, maxFirst + secondSums[j]);
            }
        }

        // 情况2：secondLen子数组在firstLen子数组之前
        int maxSecond = INT_MIN;
        for (int i = 0; i < firstSums.size(); ++i) {
            // second子数组必须在first子数组开始前结束
            int jEnd = i - 1;  // second子数组的结束索引
            int jMax = jEnd - secondLen + 1;  // second子数组的最大起始索引

            if (jMax >= 0) {
                // 更新second子数组的最大和
                if (maxSecond == INT_MIN) {
                    // 初始化maxSecond
                    for (int k = 0; k <= jMax; ++k) {
                        maxSecond = max(maxSecond, secondSums[k]);
                    }
                } else {
                    // 只需要检查新增加的可能的j
                    maxSecond = max(maxSecond, secondSums[jMax]);
                }
                maxSum = max(maxSum, maxSecond + firstSums[i]);
            }
        }

        return maxSum;
    }
};